A typical digital communication system consists of a transmitter, a transmission channel and a destination receiver. In operation, the transmitter transmits digital information from an information source over the transmission channel to the receiver. Noise, interference and distortion in the transmission channel affect the transmitted information and may cause bit errors in the information received at the destination receiver.
Various encoding techniques or codes have been employed in communication systems to minimize the effects of noise, interference and distortion. These encoding techniques enable the detection and correction of a predetermined maximum number of bit errors by adding parity data to the transmitted information. Block coding and convolutional coding are two types of coding in common use today for the transmission of digital information.
An encoder employing block coding divides the information sequence into discrete message blocks containing k information bits. The encoder generates a parity bit sequence of r bits based on the information contained in each message block. The encoder then sends each message block and corresponding parity bit sequence in a code word of N-bits, where the value N=r+k. Since the N-bit code word is generated based solely on the information in the corresponding k-bit message block, the block code encoder can be implemented using a combinational logic circuit. A general description of the block coding technique is provided in Lin, S. and Costello, Jr., D. J., Error Control Coding: Fundamentals and Applications, Chap. 3, pp. 51-84 (Prentice Hall, 1986) ("Lin and Costello"). This reference and other references mentioned in this specification are incorporated herein by reference.
An encoder utilizing convolutional codes also operates on k-bit long message blocks and generates a sequence of r parity bits to produce a corresponding code word of N-bits in length. However, the parity bits of each code word depend not only on the information in that particular k-bit message block, but also the information contained in a number of previously transmitted code words. Since the convolutional code encoder requires some means to maintain a history of the transmitted code words, it may be implemented using a sequential logic circuit. Typical convolutional coding techniques and implementations are provided in Lin and Costello, Chap. 10, pp. 287-314.
In cellular telecommunication systems, convolutional codes are the more commonly used encoding technique. Since fading of the digital signals in the cellular transmission channel occurs relatively rapidly, bit errors produced in the received information, typically occur in bursts. Although convolutional codes are a poor encoding technique for correcting bursts of bit errors because of the long decoding processing time that is required to correct such errors, reasonable decoding times can be achieved by interleaving the cellular information to be encoded.
The interleaving or scrambling of the information sufficiently randomizes the bit errors, and thus, removes the burst nature of these errors to enable convolutional coding to be an effective and practical coding method in detection and cellular telecommunication applications. An efficient decoding method for convolutional codes is the Viterbi algorithm. The Viterbi algorithm is described in detail in Blahut, R. G., Theory and Practice of Error Control Codes, Chap. 12.8, pp. 377-382 (Addison-Wesley Pub. Co. 1983) ("Blahut").
However, in certain applications, such as Personal Communications Systems or PCS, the fading of the transmitted information over a transmission channel is much slower than that of the cellular telecommunication systems. As a consequence, the burst nature of the bit errors generated in a PCS channel may not be effectively removed through the use of interleaving the information. Thus, convolutional coding may not be a desirable technique for bit error correction in PCS systems.
Reed-Solomon code is a form of block code which is commonly used to improve transmission quality of transmitted information and is particularly effective in correcting bit errors that occur in bursts. The Berlekamp-Massey algorithm, a commonly used method to decoding Reed-Solomon code, requires 2 n mathematical iterations to identify and correct a total of n symbol errors in the information message, where the number of errors n is less than or equal to the maximum number of errors the particular Reed-Solomon code system was designed to correct.
However, the mathematical iterations of the Berlekamp-Massey algorithm must be performed in a sequential fashion because the computation of a discrepancy value .DELTA..sub.r in each iteration is dependent upon the completed computation of the discrepancy value .DELTA..sub.r for the previous iteration. Further, the computation of each discrepancy value .DELTA..sub.r involves a complex and time consuming polynomial to polynomial multiplication.
An alternative prior art decoding technique for Reed-Solomon code utilizes solving a matrix inverse of the Peterson-Gorenstein-Zierler equation which requires an impractical and relatively slow n.sup.3 mathematical iterations. A general description of the Peterson-Gorenstein-Zierler equation, as well as, the Berlekamp-Massey algorithm, is provided in Blahut, Chaps. 7.2 and 7.5, pp. 166-173 and 183-191, respectively.
As the desire to send information at higher bit rates with greater error correction capabilities increases, a need to decode information at a substantially faster rate has arisen.